package stu.day47;

public class hw1 {

    public String longestPalindrome(String s) {

        while(!flag(s)){
            int[] arr = fun(s);
            String t = s.substring(arr[0],arr[1]);

            if(flag(t)){
                return t;
            }else {
                String n = s.substring(0,arr[0])+s.substring(arr[1],s.length());
                s=n;
            }
        }



        return s;

    }


    public int[] fun(String s){
        int len = s.length();
        String t= new StringBuilder(s).reverse().toString();

        int[][] dp = new int[len+1][len+1];
        int sIndex = 0;
        int max = 0;

        for (int i=1;i<=len;i++){
            for (int j=1;j<=len;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(dp[i][j]>max){
                        max = dp[i][j];
                        sIndex = i-1;
                    }
                }
            }
        }
        return new int[]{sIndex-max+1,sIndex+1};
    }

    public boolean flag(String s){
        String t = new StringBuilder(s).reverse().toString();
        return  s.equals(t);
    }



}
